package com.datastructure.test.MiniSpinnerTree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;

public class MiniSpinnerTree {

    public static void main(String[] args) {

    }

    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        HashSet<Integer> getpoint = new HashSet<>();
        //存储点
        //存储边
        Arrays.sort(cost, Comparator.comparingInt(l -> l[2]));
        //将数据添加到list中
        ArrayList<int[]> list = new ArrayList<>(Arrays.asList(cost));
        int res = 0;
        res += cost[0][2];
        getpoint.add(cost[0][0]);
        getpoint.add(cost[0][1]);
        //所有边都遍历完成，结束
        do {
            for (int i = 1; i < list.size(); i++) {//下一条为权值最小的可连接的边
                if ((getpoint.contains(list.get(i)[0])
                        && !getpoint.contains(list.get(i)[1]))
                        || (!getpoint.contains(list.get(i)[0])
                        && getpoint.contains(list.get(i)[1]))) {
                    res += list.get(i)[2];
                    getpoint.add(list.get(i)[0]);
                    getpoint.add(list.get(i)[1]);
                    list.remove(list.get(i));//去除这条已经计算过的边
                    //删除已经遍历过的这条边
                    break;
                }
            }
        } while (getpoint.size() != n);
        return res;
    }
}
